/**
 * 
 */
package leetCode;

import java.util.ArrayList;

/**
 * @author zhong
 *
 */
public class SpiralMatrixIII {

	public int[][] spiralMatrixIII(int R, int C, int r0, int c0) {
		ArrayList<int[]> path = new ArrayList<>();
		path.add(new int[] { r0, c0 });
		int[][] dir = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
		visit(r0, c0, 1, dir, 0, R, C, path);
		int[][] res = new int[path.size()][];
		for (int i = 0; i < res.length; i++) {
			res[i] = path.get(i);
		}
		return res;
	}

	private void visit(int posR, int posC, int length, int[][] dir, int dirIndex, int R, int C, ArrayList<int[]> path) {
		while (path.size() != R * C) {
			int newPosR = posR;
			int newPosC = posC;
			for (int i = 0; i < length; i++) {
				newPosR += dir[dirIndex][0];
				newPosC += dir[dirIndex][1];
				if (newPosR < R && newPosR >= 0 && newPosC < C && newPosC >= 0) {// in bond
					path.add(new int[] { newPosR, newPosC });
				}
			}
			dirIndex++;
			if (dirIndex == 2) {
				length++;
			}
			if (dirIndex == 4) {
				dirIndex = 0;
				length++;
			}
			posR = newPosR;
			posC = newPosC;
		}

	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int R = 1, C = 4, r0 = 0, c0 = 0;
		int[][] pa = new SpiralMatrixIII().spiralMatrixIII(R, C, r0, c0);
		for (int[] is : pa) {
			System.out.println("(" + is[0] + "," + is[1] + ")");
		}
	}

}
